package keni.html.android.framework.util;

import java.util.LinkedList;


public final class TopologicalSortAlgo {
	
	public static IVertex[] Sort(IVertex[] graphNodes)
	{
		ColorsSet colors = new ColorsSet(graphNodes);
		TimestampSet discovery = new TimestampSet();
		TimestampSet finish = new TimestampSet();
		LinkedList<IVertex> list = new LinkedList<IVertex>();

		Integer time = new Integer(0);

		for(IVertex node : graphNodes)
		{
			if (colors.ColorOf(node) == VertexColor.White)
			{
				Visit(node, colors, discovery, finish, list,  time);
			}
		}

		return list.toArray(new IVertex[list.size()]);
	}

	private static void Visit(IVertex node, ColorsSet colors, TimestampSet discovery, TimestampSet finish, LinkedList<IVertex> list, Integer time)
	{
		colors.Set(node, VertexColor.Gray);

		discovery.Register(node, time++);

		for (IVertex child : node.getAdjacencies())
		{
			if (colors.ColorOf(child) == VertexColor.White)
			{
				Visit(child, colors, discovery, finish, list,  time);
			}
		}

		finish.Register(node, time++);

		list.addFirst(node);

		colors.Set(node, VertexColor.Black);
	}
}
